ABC173 C - H and V

問題

問題分の詳細は省くけどようするに全探索問題。

制約が十分に少なく計算して解くのもむずかしいため全探索が模範解答。

一般的にこういう問題はbit全探索で解くようなんだけど、きりみんちゃんはbit操作にアレルギーレベルの苦手意識があるので、出来ればbit全探索ではなく、より人間にも読みやすい(※諸説あり)再帰による全探索で解きたかった。

コンテスト本番では解くことが出来なかったけど、ちゃんと再帰で解けたので紹介したいと思う。

再帰全探索で解く

とりあえずACしたコード。

code:Kotlin

fun problem173c(h: Int, w: Int, k: Int, c: List<CharArray>): Int {

var count = 0

fun isK(list: Array<CharArray>) = list.sumBy { it.count { it == '#' } } == k

fun allSearch(current: Int, ignoreY: MutableList<Boolean>, ignoreX: MutableList<Boolean>) {

if (ignoreY.size + ignoreX.size == h + w) {

val list = Array(h) { CharArray(w) { '.' } }

for (i in 0 until h) {

for (j in 0 until w) {

}

}

if (isK(list)) count++

return

}

if (current < h) {

val tmp1 = ignoreY.toMutableList()

tmp1.add(true)

allSearch(current + 1, tmp1, ignoreX)

val tmp2 = ignoreY.toMutableList()

tmp2.add(false)

allSearch(current + 1, tmp2, ignoreX)

} else {

val tmp1 = ignoreX.toMutableList()

tmp1.add(true)

allSearch(current + 1, ignoreY, tmp1)

val tmp2 = ignoreX.toMutableList()

tmp2.add(false)

allSearch(current + 1, ignoreY, tmp2)

}

}

allSearch(0, mutableListOf(), mutableListOf())

return count

}

再帰全探索の基本的な考え方は、現在の桁(current)を１ずつ進めながら、その桁が取りうる全ての値を再帰で固定し桁を進める。

この場合、取りうる値とは「その行または列を無視するかどうか」の二択なので、Boolean型でtrueとfalseにしている。

関数の引数であるignoreYとignoreXはそれぞれ「trueならその行または列を無視する」という組み合わせを記憶したリストだ。

この２つのリストは最初は空で、currentと共に１ずつ要素が増えていく。

具体的には

code:Kotlin

// current, ignoreY, ignoreX

debug： [0, [], []]

のように増えていく。

これはそれぞれの桁を増やしながらtrueとfalseを両方呼んでいるため、どんどん分岐していって

code:Kotlin

このように全パターンが呼ばれていく。

最後まで桁を進め全ての桁を固定しきったら判定を行いretrunする。

次の部分はそれぞれの組み合わせが確定した最後に使われる部分で、やっていることはignoreYとignoreXの情報を元に指定された行または桁を削ったリストを生成し、それを問題の条件に一致しているかの判定関数に渡しているだけだ。

code:Kotlin

if (ignoreY.size + ignoreX.size == h + w) {

val list = Array(h) { CharArray(w) { '.' } }

for (i in 0 until h) {

for (j in 0 until w) {

}

}

if (isK(list)) count++

return

}

この問題が少しむずかしいのは、全探索の対象が１つではなく縦横の２つあることだ。

こういう場合は、縦と横を合わせた合計の桁数を最終的な組み合わせの桁数として扱うことで対処出来た。

code:Kotlin

if (current < h) {

val tmp1 = ignoreY.toMutableList()

tmp1.add(true)

allSearch(current + 1, tmp1, ignoreX)

val tmp2 = ignoreY.toMutableList()

tmp2.add(false)

allSearch(current + 1, tmp2, ignoreX)

} else {

val tmp1 = ignoreX.toMutableList()

tmp1.add(true)

allSearch(current + 1, ignoreY, tmp1)

val tmp2 = ignoreX.toMutableList()

tmp2.add(false)

allSearch(current + 1, ignoreY, tmp2)

}

この if(current < h)の判定は、「今いる桁数が縦の桁数(h)未満だったらignoreYを操作対象として、それ以上だったら横(ignoreX)を操作対象とし、処理を続ける」ということをやっている。

今回のような問題ではパターンが2値の組み合わせなので、bit全探索で考えた方がむしろ直感的なような気もするけど、やっぱり全探索は再帰で書けると気持ちがよい。